package com.example.demo.leetcode.classics150;

import java.util.List;

/**
 * ******************************************************
 *
 * @author liugh9
 * @version 1.0
 * @classname _144不同路径II
 * @description
 * @date 2023/08/27 11:41
 * <p>
 * ******************************************************
 */
public class _144不同路径II {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int n = obstacleGrid.length;
        int m = obstacleGrid[0].length;
        int[][] dp = new int[n][m];
        //(0,0)这个格子可能有障碍物
        dp[0][0] = (obstacleGrid[0][0] == 1) ? 0 : 1;
        //处理第一列
        for (int i = 1; i < n; ++i) {
            if (obstacleGrid[i][0] == 1 || dp[i - 1][0] == 0) {
                dp[i][0] = 0;
            } else {
                dp[i][0] = 1;
            }
        }
        //处理第一行
        for (int j = 1; j < m; ++j) {
            if (obstacleGrid[0][j] == 1 || dp[0][j - 1] == 0) {
                dp[0][j] = 0;
            } else {
                dp[0][j] = 1;
            }
        }
        for (int i = 1; i < n; ++i) {
            for (int j = 1; j < m; ++j) {
                //如果当前格子是障碍物
                if (obstacleGrid[i][j] == 1) {
                    dp[i][j] = 0;
                    //路径总数来自于上方(dp[i-1][j])和左方(dp[i][j-1])
                } else {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }
        }
        return dp[n - 1][m - 1];
    }


}
